#include <iostream>

using namespace std;

class SortImpl
{
public:
    virtual void sort(int[], int) = 0;
};

class SortBubble : public SortImpl
{
public:
    void sort(int v[], int n)
    {
        for (int i = n-1; i > 0; i--)
            for (int j = 0; j < i; j++)
                if (v[j] > v[j+1])
                {
                    int t = v[j];
                    v[j] = v[j+1];
                    v[j+1] = t;
                }
        cout << "Bubble: ";
        for (int k = 0; k < n; k++)
            cout << v[k] << ' ';
        cout << '\n';
    }
};

class SortShell : public SortImpl
{
public:
    void sort(int v[], int n)
    {
        for (int g = n/2; g > 0; g /= 2)
            for (int i = g; i < n; i++)
                for (int j = i - g; j >= 0; j -= g)
                    if (v[j] > v[j+g])
                    {
                        int temp = v[j];
                        v[j] = v[j+g];
                        v[j+g] = temp;
                    }
        cout << "Shell:  ";
        for (int k = 0; k < n; k++)
            cout << v[k] << ' ';
        cout << '\n';
   }
};

class Stat
{
private:
    SortImpl* m_pImpl;
    int m_min;
    int m_max;
    int m_med;

public:
    Stat()
    {
        m_pImpl = new SortBubble();
    }

    void upGrade()
    {
        delete m_pImpl;
        m_pImpl = new SortShell();
    }

    void downGrade()
    {
        delete m_pImpl;
        m_pImpl = new SortBubble();
    }

    int getMin() { return m_min; }
    int getMax() { return m_max; }
    int getMed() { return m_med; }

    void readVector(int v[], int n)
    {
        m_pImpl->sort(v, n);
        m_min = v[0];
        m_max = v[n-1];
        m_med = v[n/2];
    }
};

int main(int argc, char** argv)
{
    const int NUM = 9;
    int array1[NUM], array2[NUM];
    srand(time(0));
    cout << "Vector: ";

    for (int i=0; i < NUM; ++i)
    {
        array1[i] = array2[i] = rand() % 9 + 1;
        cout << array1[i] << ' ';
    }
    cout << '\n';

    Stat obj;
    obj.upGrade();
    obj.readVector(array1, NUM);
    cout << "min is " << obj.getMin() << ", max is " << obj.getMax() <<
            ", median is " << obj.getMed() << '\n';

    obj.downGrade();
    obj.readVector(array2, NUM);
    cout << "min is " << obj.getMin() << ", max is " << obj.getMax() <<
            ", median is " << obj.getMed() << '\n';

    return 0;
}

